/**
 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
 * 思路我们用一个大根堆实时维护数组的前 kk 小值。首先将前 kk 个数插入大根堆中，随后从第 k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，
 * 就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。
 *
 *
 */
class Intcmp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}
public class SmallestK {
    public int[] smallestK(int[] arr, int k) {
        int[] ret=new int[k];
        if(k==0){
            return ret;
        }
        Intcmp intcmp=new Intcmp();
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(k,intcmp);
        for(int i=0;i<arr.length;i++){
            if(i<k){
                maxHeap.offer(arr[i]);
            }else{
                int top=maxHeap.peek();
                if(arr[i]<top){
                    maxHeap.poll();
                    maxHeap.offer(arr[i]);
                }
            }
        }
        for(int i=0;i<k;i++){
            ret[i]=maxHeap.poll();
        }
        return ret;
    }
}